//给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。 
//
// 二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求
//： 
//
// 
// 路径途经的所有单元格都的值都是 0 。 
// 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。 
// 
//
// 畅通路径的长度 是该路径途经的单元格总数。 
//
// 
//
// 示例 1： 
//
// 
//输入：grid = [[0,1],[1,0]]
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
//输出：4
// 
//
// 示例 3： 
//
// 
//输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
//输出：-1
// 
//
// 
//
// 提示： 
//
// 
// n == grid.length 
// n == grid[i].length 
// 1 <= n <= 100 
// grid[i][j] 为 0 或 1 
// 
// Related Topics 广度优先搜索 数组 矩阵 
// 👍 106 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /*
    状态：坐标，深度
    变化：坐标的8个方向
    继续遍历的条件：值是0
    状态变化终止的条件：1.到了终点 2.访问过了
     */
    int[][] chg = new int[][]{
            {1,0},{-1,0},
            {0,1},{0,-1},
            {1,1},{-1,-1},
            {1,-1},{-1,1}
    } ;
    public int shortestPathBinaryMatrix(int[][] grid) {
        //如果两头端点的值是1，则不通
        if(grid[0][0] == 1) return -1;
        if(grid[grid.length - 1][grid[0].length-1] == 1) return -1;
        //如果只有一个节点，且是0，那么直接返回1
        if(grid[0][0] == 0 && grid.length==1 && grid[0].length == 1){
            return 1;
        }

        int mindepth = -1;
        Map<String,Integer> visited = new HashMap<String,Integer>();

        Queue<Data> queue = new LinkedList<>();
        queue.add(new Data(0,0,1));
        visited.put(0+":"+0,1);

        while(!queue.isEmpty()){
            Data data = queue.poll();
            for(int i=0; i<chg.length; i++){
                int x = data.x + chg[i][0];
                int y = data.y + chg[i][1];


                if(x < 0 || x >= grid.length) continue;
                if(y < 0 || y >= grid[0].length) continue;
                if(grid[x][y] == 1) continue;
                if(visited.containsKey(x+":"+y)) continue;

                int curDepth = data.depth + 1;
                //到了终点了
                if(x == grid.length-1 && y == grid[0].length-1) {
                    if(mindepth == -1) {
                        mindepth = curDepth;
                        continue;
                    }
                    if(curDepth < mindepth){
                        mindepth = curDepth;
                        continue;
                    }
                }
                System.out.println("x:"+x+"\t,y:"+y);
                queue.add(new Data(x,y,curDepth));
                visited.put(x+":"+y,1);
            }
        }
        return mindepth;
    }
    class Data{
        int x;
        int y;
        int depth;

        public Data(int x, int y, int depth) {
            this.x = x;
            this.y = y;
            this.depth = depth;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
